We study the set of output stable configurations of chemical reactiondeciders (CRDs). It turns out that CRDs with only bimolecular reactions (whichare almost equivalent to population protocols) have a special structure thatallows for an algorithm to efficiently compute their finite set of minimaloutput unstable configurations. As a consequence, a relatively large set ofconfigurations may be efficiently checked for output stability. We also provide a number of observations regarding the semilinearity resultof Angluin et al. [Distrib. Comput., 2007] from the context of populationprotocols (which is a central result for output stable CRDs). In particular, weobserve that the computation-friendly class of totally stable CRDs has equalexpressive power as the larger class of output stable CRDs.
展开▼
